首页 > 试题广场 >

剪绳子

[编程题]剪绳子
  • 热度指数：257548 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

数据范围：
进阶：空间复杂度 ，时间复杂度

输入描述:
输入一个数n，意义见题面。


输出描述:
输出答案。
示例1

输入

8

输出

18

说明

8 = 2 +3 +3 , 2*3*3=18
示例2

输入

2

输出

1

说明

m>1，所以切成两段长度是1的绳子
算法知识视频讲解
查看答案及解析
添加回答
推荐
C/C++
天命剑主头像 天命剑主 
//
// Created by yuanhao on 2019-9-3.
//

#include <iostream>
#include <cmath>

using namespace std;

/**
 * 题目分析：
 * 先举几个例子，可以看出规律来。
 * 4 ： 2*2
 * 5 ： 2*3
 * 6 ： 3*3
 * 7 ： 2*2*3 或者4*3
 * 8 ： 2*3*3
 * 9 ： 3*3*3
 * 10：2*2*3*3 或者4*3*3
 * 11：2*3*3*3
 * 12：3*3*3*3
 * 13：2*2*3*3*3 或者4*3*3*3
 *
 * 下面是分析：
 * 首先判断k[0]到k[m]可能有哪些数字，实际上只可能是2或者3。
 * 当然也可能有4，但是4=2*2，我们就简单些不考虑了。
 * 5<2*3,6<3*3,比6更大的数字我们就更不用考虑了，肯定要继续分。
 * 其次看2和3的数量，2的数量肯定小于3个，为什么呢？因为2*2*2<3*3，那么题目就简单了。
 * 直接用n除以3，根据得到的余数判断是一个2还是两个2还是没有2就行了。
 * 由于题目规定m>1，所以2只能是1*1，3只能是2*1，这两个特殊情况直接返回就行了。
 *
 * 乘方运算的复杂度为：O(log n)，用动态规划来做会耗时比较多。
 */
long long n_max_3(long long n) {
    if (n == 2) {
        return 1;
    }
    if (n == 3) {
        return 2;
    }
    long long x = n % 3;
    long long y = n / 3;
    if (x == 0) {
        return pow(3, y);
    } else if (x == 1) {
        return 2 * 2 * (long long) pow(3, y - 1);
    } else {
        return 2 * (long long) pow(3, y);
    }
}

//给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
//
//输入描述:
//输入一个数n，意义见题面。（2 <= n <= 100）
//
//
//输出描述:
//输出答案。
//示例1
//输入
//8
//输出
//18
int main() {
    long long n = 0;
    cin >> n;
    cout << n_max_3(n) << endl;
    return 0;
}

编辑于 2021-07-06 10:46:45 回复(61)
Python 3
木有粗面201904101731812头像 木有粗面201904101731812
分析题意可知拆分成最多的3有最大值，再讨论剩下的情况 
class Solution:
    def cutRope(self , n: int) -> int:
        if n == 2: return 2
        if n == 3: return 3
        res = 1
        resn = n
        while resn > 2:
            resn -= 3
            res = res*3
        if resn == 1:
            res = res // 3 * 4
        if resn == 2:
            res = res * 2
        return res



发表于 2022-09-15 14:14:51 回复(0)
Python 3
牛客535534164号头像 牛客535534164号 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def cutRope(self , n: int) -> int:
        # write code here
        if n == 0:
            return 0
        else:
            dp = [i for i in range(n+1)]
            dp[0] = 1
            for i in range(n+1):
                max_n = 0
                for j in range(i+1):
                    max_n = max(max_n , dp[i-j] * dp[j])
                dp[i] = max_n
        return dp[n]

发表于 2022-08-17 15:20:15 回复(0)
Python 3
Vivimore头像 Vivimore 
class Solution:
    def cutRope(self , number: int) -> int:
        if number <= 3:
            return number - 1
        a, b, c = 1, 2, 3
        for i in range(4, number+1):
            res = max(c, 2 * b, 3 * a)
            a = b
            b = c 
            c = res
        return res
class Solution:
    def cutRope(self , n: int) -> int:
        # 不超过3直接计算
        if n <= 3:
            return n - 1
        res = 1
        while n > 4:
            res *= 3
            n -= 3
        return res * n
class Solution:
    def cutRope(self , n: int) -> int:
        # 不超过3直接计算
        if n <= 3:
            return n - 1
        # dp[i]表示长度为i的绳子可以被剪出来的最大乘积
        dp = [0 for i in range(n + 1)]
        dp[1] = 1
        dp[2] = 2
        dp[3] = 3
        dp[4] = 4
        # 遍历后续每一个长度
        for i in range(5, n + 1):
            # 可以被分成各种长度的两份
            for j in range(1, i):
                # 取最大值
                dp[i] = max(dp[i], j * dp[i - j])
        return dp[n]
发表于 2022-05-12 21:20:00 回复(0)
Python 3
kinter1头像 kinter1 
class Solution:
    def cutRope(self , number: int) -> int:
        n = number
        max_value = 1
        for m in range(2 ,n):
            km = round(n / m)
            temp = n - (km * (m - 1))
            value = km ** (m-1) * temp

            max_value = max(max_value, value)
        return max_value
基本不等式，绳子划分成m段的时候，根据基本不等式k1=k2=...=km时取最大，所以我们可以遍历从2段到n段，每段尽量取相等，算出来面积一定最大
发表于 2022-03-12 16:06:23 回复(0)
Python 3
撒旦法说头像 撒旦法说 
class Solution:
    def cutRope(self , number: int) -> int:
        # write code here
        l=[]
        for i in range(2,number+1):
            x=number//i
            lf=number-x*i
            res=x**(i-lf)*(x+1)**lf
            l.append(res)
        return max(l)

发表于 2021-12-23 21:53:09 回复(0)
Python 3
拍喉离谱肉头像 拍喉离谱肉

根据算术-几何平均不等式推测各段绳子长度分得越平均它们的乘积就越大，因此我们只要找一条绳子平均分成2段、3段至number//2段中的乘积最大值就好了
图片说明 

class Solution:
    def cutRope(self , number: int) -> int:
        return max([(number//m+1)**(number%m)*(number//m)**(m-number%m) for m in range(2,number//2+1)])
发表于 2021-11-17 11:00:23 回复(0)
Python 3
牛客736356489号头像 牛客736356489号 
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        if number<=3: return number
        res=[1,2,3]
        for i in range(4,number+1):
            res.append(i)
            for j in range(2,i//2+1):
                if res[j-1]*res[i-j-1]>res[-1]:
                    res[-1]=res[j-1]*res[i-j-1]
        return res[-1] # 干就玩了

发表于 2021-10-17 15:13:11 回复(0)
Python 3
给个offer吧！！！！头像 给个offer吧！！！！ 
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        result = 1
        if number == 2:
            return 1
        while (number - 3) > 1:
            result *= 3
            number -= 3
        result *= number
        
        return result

发表于 2021-09-13 22:30:21 回复(0)
Python 3
牛客38477449号头像 牛客38477449号 
# -*- coding:utf-8 -*-
import math
class Solution:
    def cutRope(self, number):
        # write code here
        if number < 3:
            return number
        m, n = number // 3, number % 3
        if n == 1:
            return int(math.pow(3, m-1) * 4)
        elif n == 0:
            return int(math.pow(3, m))
        else:
            return int(math.pow(3, m) * n)

发表于 2021-09-03 23:39:33 回复(0)
Python 3
可恶，被他装到了头像 可恶，被他装到了
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        result = 1
        while number > 4:
            result *= 3
            number -= 3
        result *= number
        return result
        
        # write code here
发表于 2021-08-19 18:03:43 回复(0)
Python 3
三水123头像 三水123 
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        count = 1
        if number == 4:
            return 4
        if number == 3:
            return 2
        if number == 2:
            return 1
        while number>4:
            number -= 3
            count *= 3
            
        if number ==0:
            return count
        else:
            return number * count


发表于 2021-08-12 21:56:10 回复(0)
Python 3
tantantansq头像 tantantansq 
class Solution:
    def cutRope(self, number):
        # write code here
        n=int(number/3)
        k=number%3
        if k==0:
            return 3**n 
        if k==1:
            return 3**(n-1)*4
        if k==2:
            return 3**n*2

发表于 2021-08-09 01:07:53 回复(0)
提交观点

问题信息

基础数学
上传者：小小
难度：
13条回答 68363浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号